1. Field of the Invention
The present invention relates to a management method and device in a circuit-switched communication network using an improved summarised representation of the network. Furthermore, the present invention relates to a routing method and device, to a pricing method and device and to a planning method and device in a circuit-switched communication network.
2. Description of the Related Art
Communication networks comprise a set of nodes interconnected with links to permit the exchange of information which may be voice, sound, graphics, pictures, video, text or data. The nodes-are divided into two types: terminal nodes and communication nodes. The terminal nodes, such as phone sets, computers, printers, file servers or video monitors, generate or use the information transmitted over the network. The communication nodes, such as switches or gateways relay the information but do not generate or use it. The communication from some terminal node A to terminal node B takes place over one or more communication links. The physical medium that supports this communication may be a cable, copper wires, an optical fiber or a radio link, for instance.
A need to exchange information between two nodes is called a demand. Demands can either be uni- or bi-directional, or do not require that the same amount of bandwidth be transmitted in both ways. However, links are bi-directional. Networks requiring the establishment of a connection before information can be transferred between nodes are called circuit-switched communication networks. In those networks, a circuit is established only on demand and is deallocated when no longer needed. Circuit-switched communication networks can use a variety of protocols such as, for instance, Asynchronous Transfer Mode (ATM), Time Division Multiplexing (TDM), Resource Reservation Protocol (RSVP), Transmission Control Protocol (TCP) and Synchronous Digital Hierarchy (SDH). Common circuit-switched communication networks need at least some form of management of resources and demands arising in the network. Most circuit-switched networks are centrally managed (not TCP however). A central hardware and software management platform manages and routes, usually in “real-time”, all new demands through the network. The central management platform may perform other tasks such as pricing and analysis functions to study the network load, identify bottlenecks, and so on.
Each link in the network may be characterised by at least one metric such as the bandwidth available on the link. Some circuit-switched communication networks such as, for example, ATM, allows management based on quality of service (QoS) requirements. Each new demand may contain a quality of service parameter indicating the amount of resources the calling user requires for the communication he wants to establish. A typical resource that may be requested would be, for instance, the bandwidth: a caller in an ATM network can request establishment of, a connection with at least 64 Kbit/second for instance. However, in order to support a wide range of applications, new routing protocols may use quality of service parameters defined with multiple metrics such as bandwidth, delay and loss probability Zheng Wang and Jon Crowcroft describe in “Quality-of-Service Routing for Supporting Multimedia Applications”, IEEE Journal on Selected Areas in Communications, vol. 14, no 7, p. 1228, September 1996, a strategy to find a path satisfying several requirements. For instance, this method allows a path to be found with maximum bottleneck bandwidth (the widest path), and when there are more than one widest path, the one with the shortest propagation delay.
The central platform usually comprises an electronic memory storing some form of representation of the state of the network at the time considered. This representation usually includes information about the topology of the network, i.e., a list of nodes and links interconnecting those nodes. The representation stored in said memory usually also contains some information about circuits already established across the network and, in some cases, about demands for establishing new circuits across the network.
In a centrally managed network, the central management platform is usually responsible for routing demands, i.e., for determining a route across the network for each new demand. The efficiency of the routing means, i.e., its ability to find a <<good>> route for most new demands, depends not only on the routing algorithm used, but also on the stored representation of the state of the network. For very big networks, it becomes no longer possible to store and update in the RAM of the management platform a complete representation of the network and to work in real time on it. It may be possible to reduce the size of said representation by aggregating at least some subnetworks in single nodes. However, if said representation is incomplete, the routing means are likely not to be able to find a good route. Even if it is possible to work on a complete representation of the network, the time needed by the routing means to find a circuit through a huge amount of nodes may become no longer acceptable. In other words, there is a trade-off between the size of the network and the admissible time for finding a route for new demands.
In most communication networks, the price of a communication is computed based on the connection duration only (Internet), on connection and bandwidth (some Internet providers), or on duration, time of the day and distance (telephone network). Networks with a dynamic pricing policy have also been experimented with: in this case, the price of a connection through a link depends on the resources available on that link. In a centrally managed network, the price for a new communication may be computed by the central management platform based on its knowledge of the state of the network at time t. Dynamic price procedures therefore also require the central platform to store at least some form of representation of the network's state or topology.
Network planning tools are used for analysing the behaviour of an existing network and/or planning the construction of a new network or the modification (extension) of an existing network. They may use a network simulator for generating the expected demands, or import them from, e.g., measurement tools. They can be used as stand-alone devices or may be connected to an existing network. Network planning tools usually use a memory to store a representation of the topology of the network. The operator can then observe the behaviour of the network in order to plan improvements to the network. Working on a complete representation of very big networks need however huge memories and very expensive computers to be performed in a reasonable time. Network planning tools therefore sometimes use a summarised representation of the network with subnetworks aggregated in a single node. This summarised representation may however hide bottlenecks inside aggregated subnetworks. Moreover, it may be difficult even for an experienced operator to point out problems which may occur in a network, specially in a network containing thousands or even millions of nodes.
Routing means, price procedure determination means and network planning tools therefore all need to store and/or work on some form of dynamic representation of the state of the network. When the size of the network grows, the size of its representation grows accordingly, and it becomes difficult to work on such a big representation.
One technical problem the invention wishes to solve is to find an improved method of management of demands and resources in a centrally managed circuit-switched communication network that uses an improved representation of the state of the network. In particular, one technical problem the invention aims to solve is to find an improved routing method and an, improved pricing method. One other technical problem the invention aims to solve is to find an improved network planning method which can be distributed or performed on a central management platform in a centrally managed circuit-switched communication and/or on a stand-alone general purpose computer, wherein the improved network planning method uses an improved representation of the state of the network.
In order to manage big networks, it has been proposed that network management functions be distributed to local agents, each local agent being responsible for a limited subset of nodes in the network. A node requesting establishment of a new connection may ask its local master to find a route and determine the price of the connection. Agents co-operate to ensure routing through the whole network. The structure of agents is hierarchised: higher-level agents arbitrate disputes between peer agents which cannot be solved otherwise. A local agent may for instance try to find a path across the network based upon the requested quality of service and its knowledge of the network state; if it fails, or if the destination node does not belong to the subset it rules, the local agent may ask a higher-level agent to solve the problem. This establishment of a new connection may ask its local master to find a route and determine the price of the connection. Agents cooperate to ensure routing through the whole network. The structure of agents is hierarchised: higher-level agents arbitrate disputes between peer agents which cannot be solved otherwise. A local agent may for instance try to find a path across the network based upon the requested quality of service and its knowledge of the network state; if it fails, or if the destination node does not belong to the subset it rules, the local agent may ask a higher-level agent to solve the problem. This distributed management needs at least some signalling protocols to be established between local agents. For instance, information about link metrics and about the state of particular nodes must be shared between local agents.
Such a distributed management is described by Anthony Alles of Cisco Systems, Inc, in “ ATM Internetworking”, May 1995. General information about management of demands and resources in an ATM network are given by David E. McDysan and Darren L. Spohn in “ATM—Theory and Application”, McGraw-Hill Series on Computer Communications, 1994, ISBN 0-07-060362-6. Fergal Somers of Ericsson Applied Laboratory in Network Management describes in “HYBRID: Intelligent Agents for Distributed ATM Network Management” an ATM network managed by a hierarchy of distributed agents. Each agent manages resources and demands in an arbitrarily and statically defined subnetwork, in most cases an administrative domain of some kind. For instance, a university could be managed as follows: an agent is in charge in each lab, whereas other agents each oversee a department and a single one rules the university.
It would not be possible for every local agent in a very big network with distributed management to store a complete representation of the state of the complete network. For that reason, the representation of the state of the network in each local agent and in the signalling messages transmitted between local agents is sometimes summarised by replacing aggregated sets of nodes by a single node.
One technical problem the invention wishes to solve is thus to find an improved distributed method of management of demands and resources in a circuit-switched communication network that uses an improved representation of the state of the network.
One other problem the invention wishes to solve is to find an improved hierarchy of distributed agents for managing a circuit-switched communication network.